# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]: 
        """
            递归实现
        """
        rst = []
        def postorder(node):
            if not node:
                return     

            postorder(node.left)
            postorder(node.right)
            rst.append(node.val)
        
        postorder(root)

        return rst


    def postorderTraversal1(self, root: TreeNode) -> List[int]: 
        """
            显示栈: 后序遍历，没想到常规的解法。 就是不能直接用显示栈求， 前序是 根，左，右。  变换为 根，右， 左
            恰好是后序遍历反过来的结果~ 
        """
        if not root: return []

        stack = list()
        stack.append(root)

        rst = []
        while stack:
            curNode = stack.pop()
            # 1. 拿到栈顶节点，值入栈
            rst.append(curNode.val)
            # 2. 右左节点各入栈，先入right ，则left在栈顶，先计算
            if curNode.left: stack.append(curNode.left)
            if curNode.right: stack.append(curNode.right)

        return rst[::-1]
    
    
    # 自己写的显示栈
    def postorderTraversal(self, root: TreeNode) -> List[int]: 
        """
            显示栈
        """
        if not root: return []
        stack = list()
        stack.append(root)
        rst = []
        # pre代表上一个节点， 可能是左子节点， 也可能是右子节点。当为了证明当前节点，进行过搜索，它的子节点已经遍历过了
        pre = TreeNode()
        while stack:
            cur = stack[-1]
            while cur and cur.right != pre and cur.left != pre:
                # 根右左进，左右根出
                # 1. 如果存在 有节点，加入栈 
                if cur.right:
                    stack.append(cur.right)
                # 2. 如果存在左节点，加入栈
                if cur.left:
                    stack.append(cur.left)
                    cur = cur.left
                # 3. 按照左右根的顺序，不存在左节点， 要往右节点继续遍历
                else:
                    cur = cur.right

            # 当前栈顶节点
            node = stack.pop()
            rst.append(node.val)
            pre = node
        
        return rst


    def postorderTraversal(self, root: TreeNode) -> List[int]:
        """
            官网的解法，代码思想类似于中序遍历，感觉更加合理。更像是递归思路推导而来
        """
        if not root:
            return list()
        
        res = list()
        stack = list()
        prev = None

        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            if not root.right or root.right == prev:
                res.append(root.val)
                prev = root
                root = None
            else:
                stack.append(root)
                root = root.right
        
        return res

